//454. 四数相加 II
function fourSumCount_five(A: number[], B: number[], C: number[], D: number[]): number {
    let n = A.length
    let map = new Map<number,number>()
    D.map(v=>{
        let num = map.get(v)||0
        map.set(v,num+1)
    })
    let ans = 0
    for(let i=0;i<n;i++){
        for(let j=0;j<n;j++){
            for(let k=0;k<n;k++){
                let left = - (A[i]+B[j]+C[k])
                let num = map.get(left)|| 0
                ans += num
            }
        }
    }
    return ans
};

function fourSumCount(A: number[], B: number[], C: number[], D: number[]): number {
    let n = A.length
    let map = new Map<number,number>()
    for(let i=0;i<n;i++){
        for(let j=0;j<n;j++){
            let sum = A[i]+B[j]
            let num = map.get(sum)||0
            map.set(sum,num+1)
        }
    }

    let ans = 0
    for(let i=0;i<n;i++){
        for(let j=0;j<n;j++){
            let sum = C[i]+D[j]
            let num = map.get(-sum)||0
            ans+=num
        }
    }
    return ans
};


/**
 * 这个题是4个不同的数组,只需要两两相加，然后hash就行
 * 
 * 排序再n-1次循环加双指针是一个数组
 * 时间复杂度就是n-1
 */